package leetcode.editor.cn;

//给定一个非空的正整数数组 nums ，请判断能否将这些数字分成元素和相等的两部分。
//
//
//
// 示例 1： 123123
//
//
//输入：nums = [1,5,11,5]
//输出：true
//解释：nums 可以分割成 [1, 5, 5] 和 [11] 。
//
// 示例 2：
//
//
//输入：nums = [1,2,3,5]
//输出：false
//解释：nums 不可以分为和相等的两部分
//
//
//
//
//
//
//
// 提示：
//
//
// 1 <= nums.length <= 200
// 1 <= nums[i] <= 100
//
//
//
//
//
// 注意：本题与主站 416 题相同： https://leetcode-cn.com/problems/partition-equal-subset-
//sum/
//
// Related Topics 数学 字符串 模拟 👍 96 👎 0

public class NUPfPr {
    public static void main(String[] args) {
        Solution solution = new NUPfPr().new Solution();

    }

    //leetcode submit region begin(Prohibit modification and deletion)
    class Solution {
        public boolean canPartition(int[] nums) {
            int n = nums.length;
            if (n < 2) {//如果数组长度小于2，则无法分割成两半
                return false;
            }
            int sum = 0, maxNum = 0;
            for (int num : nums) {//计算数组中所有数字的和，并找出最大值
                sum += num;
                maxNum = Math.max(maxNum, num);
            }
            if (sum % 2 != 0) {//如果数组中所有数字的和为奇数，则无法分割成两半
                return false;
            }
            int target = sum / 2;
            if (maxNum > target) {//如果数组中某个数字大于数组和的一半，则无法分割成两半，因为最大值已经不可能分割了
                return false;
            }
            // 创建一个二维数组，用于记录状态转移方程；dp[i][j]表示前i个数字中是否存在子集的和为j.也就是从前i个数字中能否选取元素，使和为j
            boolean[][] dp = new boolean[n][target + 1];
            for (int i = 0; i < n; i++) {//初始化第一列，如果前i个数字的和为0，则一定存在子集的和为0
                dp[i][0] = true;
            }
            dp[0][nums[0]] = true;//从[0,0],只有一个数字，所以只有一种可能，即选取这个数字
            for (int i = 1; i < n; i++) {//遍历数组中的每个数字
                int num = nums[i];//当前遍历到的数字
                for (int j = 1; j <= target; j++) {
                    if (j >= num) {//说明当前的target 大于数组最后一个数字，则当前数字可选可不选；不选取，则当前数字的前i-1个数字的和为j，也可以选取当前数字，则当前数字的前i-1个数字的和为j-num
                        dp[i][j] = dp[i - 1][j] | dp[i - 1][j - num];
                    } else {//说明说明当前的target 小于等于数组最后一个数字，一定不会选取；则只能当前数字的前i-1个数字的和为j
                        dp[i][j] = dp[i - 1][j];
                    }
                }
            }
            return dp[n - 1][target];
        }
    }

//leetcode submit region end(Prohibit modification and deletion)

}
